package leetcode81_90;

import org.junit.Test;

/**
 * @author shhjiang_001
 * @create 2020-06-25 9:54
 */
                /*
                给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
                求在该柱状图中，能够勾勒出来的矩形的最大面积。
                        示例:

                        输入: [2,1,5,6,2,3]
                        输出: 10
                        */

public class Solution84 {
    int res = 0;
    public int largestRectangleArea(int[] heights) {
        int le = 0;
        int ri = heights.length-1;
        method(le,ri,heights);
        return res;
    }

    private void method(int le, int ri, int[] heights) {
        if (le == ri){
            res = Math.max(res,heights[le]);
            return;
        }else if (le > ri){
            return;
        }
        int minValue = Integer.MAX_VALUE;
        int minIndex = le;
        for (int i = le; i <= ri; i++) {
            if (heights[i] < minValue){
                minValue = heights[i];
                minIndex = i;
            }
            minValue = Math.min(minValue,heights[i]);
        }
        res = Math.max(res,minValue*(ri+1-le));
        method(le,minIndex-1,heights);
        method(minIndex+1,ri,heights);
    }

    @Test
    public void test(){
        largestRectangleArea(new int[]{2,1,5,6,2,3});
//        System.out.println(Integer.parseInt("123   ".trim()));
        String[] split = "[1,2,3,4,5]".substring(1,10).split(",");
        System.out.println(split);
    }
}
